note:两个字符串匹配的问题,经典的解法就是使用二维dp数组进行动态规划求解,因为显然字符串匹配就是一个可以分解为小问题、依赖小问题来解决大问题的问题。
题目描述
请实现一个函数用来匹配包含’. ‘和’*‘的正则表达式。模式中的字符’.’表示任意一个字符,而’*‘表示它前面的字符可以出现任意次(含0次)。在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串”aaa”与模式”a.a”和”ab*ac*a”匹配,但与”aa.a”和”ab*a”均不匹配。
示例 1:
1 | 输入: |
示例 2:
1 | 输入: |
示例 3:
1 | 输入: |
示例 4:
1 | 输入: |
示例 5:
1 | 输入: |
- s 可能为空,且只包含从 a-z 的小写字母。
- p 可能为空,且只包含从 a-z 的小写字母以及字符 ‘.’ 和’*‘,无连续的 ‘*’。
方法一: 二维动态规划
思路
两个字符串的匹配问题,可以转换为二维动态规划问题。
两个字符串的匹配是非常复杂的,但是单个的字符匹配是简单的,动态规划解决字符串匹配的问题的关键就是考虑到,我们可以转化的小问题,是匹配两个字符串的各个子串。
我们考虑使用dp[m][n]
数组来表示动态规划存储的匹配方案,$dp[i][j]$表示$s$前$i$个字符和$p$前$j$个字符是否可以匹配。
接下来我们分情况进行讨论
$p$的第$j$ 个字符是字母。由于$s$中都是字母,那么很显然如果当前两个字符相同,前面的子串可以匹配,那自然新的子串也可以进行匹配。这种情况的状态转移方程非常简单:
$p$的第$j$个字符是’.’。由于’.’可以匹配任何一个字符,那它的转移方程更为简单:
$p$的第$j$个字符是’*‘。这种情况就比较复杂了,因为’*‘的匹配规则是“它前面的字符可以出现任意次(含0次)”也就是说$p$第$j$个位置出现*号时我们就要考虑第$j-1$个字符的情况。此时我们可以列出来该字符出现若干次时的状态转移
- 出现0次:$dp[i][j] = dp[i][j-2]$。含义就是既然我第$j-1$个字符没有出现,那么我$s$字符串中的第$i$个字符就不应该和我第$j-1$个字符进行匹配,而应该和再往前一个字符匹配,也就是第$j-2$个字符。
- 出现1次并且和$s$中的第$i$个元素成功匹配:$dp[i][j]=dp[i-1][j-2]$,向前匹配
- 出现2次并且和$s$中的第$i$个、第$i-1$个元素成功匹配:$dp[i][j] = dp[i-2][j-2]$,继续向前匹配
- ·········
根据这个过程,我们可以得出一个状态转移方程
理解为当$p$中第$j-1$个元素不等于$s$中第$i$个元素时(匹配失败),就将第$j-1$个元素视作出现0次处理。将$s$中的第$i$个元素和$p$中的第$j-2$个元素对比,如果匹配成功,则考虑多种情况,既有可能虽然匹配成功,但是该元素不一定要出现(0次出现),也有可能该次出现有效,往前溯源看前面是否相同。
最后的话我们总结三种状态转移方程,得到一个整体的转移方程如下:
match(x,y)是我们做的匹配过程,为了提高程序的复用性,我们可以写成c++11标准中的lambda表达式,lambda表达式用于定义并创建匿名的函数对象,以简化编程。使用格式如下:
1 | [函数对象参数] (操作符重载函数参数) mutable ->返回类型 { |
具体介绍和使用我后面会写一篇额外的博客,这儿就不赘述了。
代码
1 | class Solution { |
复杂度分析
- 时间复杂度$O(mn)$。m、n分别为字符串长度
- 空间复杂度$O(mn)$。dp数组的大小为m*n
原文链接: https://zijian.wang/2021/06/08/19. 正则表达式匹配/
版权声明: 转载请注明出处.